home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / tex / gestalt.zip / SIMIL_A.ASM < prev    next >
Assembly Source File  |  1988-12-06  |  13KB  |  339 lines
  1. ;From the article "Pattern Matching - The Gestalt Approach"
  2. ;by John W. Ratcliff and David E. Metzener
  3. ;Dr. Dobbs Journal, July 1988
  4.  
  5. ; This version is for use in assembly language programs.
  6. ; See TESTSIM.ASM for a demonstration.
  7. ;
  8. ; -    All required local variables are right here in this procedure.
  9. ; -    Enter with DS:SI = pointer to string 1,
  10. ;           DS:DI = pointer to string 2
  11. ;    Preserves all registers except AX (which returns the similarity)
  12. ; It is CRITICAL that SS=CSeg!  Else the bp referencing will not work!
  13. ; I have no intentions of hacking it for other configurations ..
  14. ; that's left as an exercise for the student.
  15. ; (Hint:  Look in the Turbo Pascal version for an example.)
  16. ;
  17. ; David Kirschbaum
  18. ; Toad Hall
  19. ; kirsch@braggvax.ARPA
  20.  
  21.  
  22. ;TITLE    SIMIL.ASM written by John W. Ratcliff and David E. Metzener
  23.  
  24. ; November 10, 1987
  25. ; Uses the Ratcliff/Obershelp pattern recognition algorithm.
  26. ; The function SIMIL returns a percentage value corresponding to how
  27. ; alike any two strings are.  Be certain to upper case the two strings
  28. ; passed if you are not concerned about case sensitivity.
  29.  
  30. _Simil_a    proc    near
  31.  
  32. ;TH Data moved down here so it'll be completely contained in our procedure.
  33.  
  34. ststr1L    dw    25 dup(?)        ;contains lefts for string 1
  35. ststr1R    dw    25 dup(?)        ;contains rights for string 1
  36. ststr2L    dw    25 dup(?)        ;contains lefts for string 2
  37. ststr2R    dw    25 dup(?)        ;contains rights for string 2
  38. stcknum    dw    ?            ;number of elements on the stack
  39. score    dw    ?            ;the # of chars in common times 2
  40. total    dw    ?            ;total # of chars in string 1 and 2
  41. cL1    dw    ?            ;left of string 1 found in common
  42. cR1    dw    ?            ;right of string 1 found in common
  43. cL2    dw    ?            ;left of string 2 found in common
  44. cR2    dw    ?            ;right of string 2 found in common
  45. s2ed    dw    ?            ;the end of string 2 used in compare
  46.  
  47. _simil:
  48. ; This routine expects pointers passed in two character strings, null
  49. ; terminated, that you wish compared.  It returns a percentage value
  50. ; from 0 to 100% corresponding to how alike the two strings are.
  51. ; Usage:    DS:SI = pointer to string 1                TH
  52. ;        DS:DI = pointer to string 2                TH
  53. ; The similarity routine is composed of three major components
  54. ; pushst    --- pushes a string section to be compared on the stack
  55. ; popst        --- pops a string section to be examined off of the stack
  56. ; compare    --- finds the largest group of characters in common between
  57. ;            any two string sections
  58. ; The similarity routine begins by computing the total length of both
  59. ; strings passed and placing that value in TOTAL.  It then takes
  60. ; the beginning and ending of both strings passed and pushes them on
  61. ; the stack.  It then falls into the main line code.
  62. ; The original two strings are immediately popped off of the stack and
  63. ; are passed to the compare routine.  The compare routine will find the
  64. ; largest group of characters in common between the two strings.
  65. ; The number of characters in common is multiplied times two and added
  66. ; to the total score.  If there were no characters in common, then there
  67. ; is nothing to push onto the stack.  If there are exactly one character
  68. ; to the left in both strings, then we needn't push it on the stack.
  69. ; (We already know they aren't equal from the previous call to compare.)
  70. ; Otherwise the characters to the left are pushed onto the stack.  These
  71. ; same rules apply to characters to the right of the substring found in
  72. ; common.  This process of pulling substrings off of the stack, comparing
  73. ; them, and pushing remaining sections on the stack is continued until
  74. ; the stack is empty.  On return the total score is divided by the
  75. ; number of characters in both strings.  This is multiplied times 100 to
  76. ; yield a percentage.  This percentage similarity is returned to the
  77. ; calling procedure.
  78.  
  79.     push    bp        ;save BP reg.
  80.     mov    bp,sp        ;save SP reg in BP for use in program
  81.     push    bx        ;save all regs we're gonna trash    TH
  82.     push    cx
  83.     push    dx
  84.     push    si
  85.     push    di
  86.     push    ES        ;save the ES seg register
  87.  
  88.     mov    ax,DS        ;copy DS segment reg to ES
  89.     mov    ES,ax
  90.  
  91.     xor    ax,ax        ;zero out AX for clearing of SCORE var
  92.     mov    score,ax    ;zero out SCORE
  93.     mov    stcknum,ax    ;initialize number of stack entries to 0
  94. ;TH DS:SI and DS:DI already point to string 1 and string 2 respectively.
  95. ;TH    mov    si,[bp+4]    ;move beginning pointer of string 1 to SI
  96. ;TH    mov    di,[bp+6]    ;move beginning pointer of string 2 to SI
  97.  
  98.     cmp    [si],al        ;is it a null string?
  99.     je    StrErr        ;can't process null strings
  100.      cmp    [di],al        ;is it a null string?
  101.      jne    DoCmp        ;Neither is a null string, so process them
  102. StrErr:    jmp    Donit        ;exit routine
  103.  
  104. DoCmp:    push    di        ;save DI because of SCAS opcode
  105.     push    si        ;save SI because of SCAS opcode
  106.     xor    al,al        ;clear out AL to search for end of string
  107.     cld            ;set direction flag forward
  108.     mov    cx,-1        ;make sure we repeat the correct # of times
  109.  
  110.     repnz    scasb        ;scan for string delimiter in string 2
  111.     dec    di        ;point DI to '$00' byte of string 2
  112.     dec    di        ;point DI to last char of string 2
  113.     mov    bp,di        ;move DI to BP where it is supposed to be
  114.  
  115.     pop    di        ;restore SI into DI for SCAS (string 1)
  116.     repnz    scasb        ;scan for string delimiter in string 1
  117.  
  118.     not    cx        ;do one's complement for correct length of st
  119.     sub    cx,2        ;subtract the two zero bytes at the end of st
  120.     mov    total,cx    ;store string 2's length
  121.  
  122.     dec    di        ;point DI to '$00' byte of string 1
  123.     dec    di        ;point DI to last char of string 1
  124.     mov    bx,di        ;move DI to BX where it is supposed to be
  125.  
  126.     pop    di        ;restore DI to what it should be
  127.     call    PushSt        ;push values for the first call to SIMILIARITY
  128.  
  129. Main:    cmp    stcknum,0    ;is there anything on the stack?
  130.     je    Done        ;no, then all done!
  131.  
  132.     call    PopSt        ;get regs set up for a compare call
  133.     call    Compare        ;do compare for this substring set
  134.     or    dx,dx        ;if nothing in common then nothing to push TH
  135.     jz    Main        ;try another set            TH
  136.  
  137.     shl    dx,1        ;*2 for add to score
  138.     add    score,dx    ;add into score
  139.     mov    bp,stcknum    ;get number of entry I want to look at
  140.     shl    bp,1        ;get AX ready to access string stacks
  141.     mov    si,[ststr1L+bp]    ;move L1 into SI or L1
  142.     mov    bx,cL1        ;move CL1 into BX or R1
  143.     mov    di,[ststr2L+bp]    ;move L2 into DI or L2
  144.     mov    cx,cL2        ;move CL2 into CX temporarily
  145.     mov    ax,[ststr1R+bp]    ;get old R1 off of stack
  146.     mov    cL1,ax        ;place in CL1 temporarily
  147.     mov    ax,[ststr2R+bp]    ;get old R2 off of stack
  148.     mov    cL2,ax        ;save in CL2 temporarily
  149.     mov    bp,cx        ;place CL2 into BP
  150.  
  151.     cmp    bx,si        ;compare CL1 to L1
  152.     je    ChRght        ;if zero, then nothing on left side string 1
  153.  
  154.     cmp    bp,di        ;compare CL2 to L2
  155.     je    ChRght        ;if zero, then nothing on left side string 2
  156.  
  157.     dec    bx        ;point to last part of left side string 1
  158.     dec    bp        ;point to last part of left side string 2
  159.     cmp    bx,si        ;only one char to examine?
  160.     jne    PushIt        ;no->we need to examine this
  161.     cmp    bp,di        ;only one char in both?
  162.     je    ChRght        ;nothing to look at if both only contain 1 char
  163.  
  164. PushIt:    call    PushSt        ;push left side on stack
  165. ChRght:    mov    si,cR1        ;move CR1 into SI or L1
  166.     mov    bx,cL1        ;move R1 into BX or R1
  167.     mov    di,cR2        ;move CR2 into DI or L2
  168.     mov    bp,cL2        ;move R2 into BP or R2
  169.  
  170.     cmp    si,bx        ;compare CR1 to R1
  171.     je    Main        ;If zero, then nothing on right side string 1
  172.     cmp    di,bp        ;compare CR2 to R2
  173.     je    Main        ;if zero, then nothing on right side string 2
  174.  
  175.     inc    si        ;point to last part of right side string 1
  176.     inc    di        ;point to last part of right side string 2
  177.     cmp    bx,si        ;only one char to examine?
  178.     jne    Push2        ;no-> examine it
  179.     cmp    bp,di        ;only 1 char to examine in both?
  180.     je    Main        ;yes-> get next string off of stack
  181.  
  182. Push2:    call    PushSt        ;push right side on stack
  183.     jmp    short Main    ;do next level of compares
  184.  
  185. Done:    mov    ax,score    ;get score into AX for MUL
  186.     or    ax,ax        ;anything?                TH
  187.     jz    Donit        ;nope, forget this mess            TH
  188.     mov    cx,100        ;get 100 into CX for MUL
  189.     mul    cx        ;multiply by 100
  190.     mov    cx,total    ;get total chars for divide
  191.     div    cx        ;divide by total
  192. Donit:
  193.     pop    ES        ;restore ES to entry value
  194.     pop    di        ;and all other regs also        TH
  195.     pop    si
  196.     pop    dx
  197.     pop    cx
  198.     pop    bx
  199.     pop    bp        ;restore BP back to entry value
  200.     ret            ;leave with AX holding % similarity
  201.  
  202.  
  203. Compare:
  204.  
  205. ; The compare routine locates the largest group of characters between string 1
  206. ; and string 2.  This routine assumes t